#include <bits/stdc++.h>

using namespace std;

// 验证搜索二叉树
// 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution 
{
private:
    static const int MAXN = 10001;
    TreeNode* st[MAXN];
    int r;

public:
    bool isValidBST(TreeNode* root) 
    {
        if(root == nullptr) return true;

        TreeNode* pre = nullptr;
        r = 0;
        while(r > 0 || root)
        {
            while(root)
            {
                st[r++] = root;
                root = root->left;
            }
            root = st[--r];
            if(pre != nullptr && root->val <= pre->val) return false;
            pre = root;
            root = root->right;
        }
    }
};

class Solution 
{
private:
    long mn, mx;

public:
    bool isValidBST(TreeNode* root) 
    {
        if(root == nullptr)
        {
            mn = LONG_MAX;
            mx = LONG_MIN;
            return true;
        }

        bool lok = isValidBST(root->left);
        long lmax = mx, lmin = mn;
        bool rok = isValidBST(root->right);
        long rmax = mx, rmin = mn;
        mx = max(max(lmax, rmax), (long)root->val);
        mn = min(min(lmin, rmin), (long)root->val);
        return lok && rok && lmax < root->val && root->val < rmin;
    }
};

class Solution 
{
private:
    long prev = LONG_MIN;

public:
    bool isValidBST(TreeNode* root) 
    {
        if(root == nullptr) return true;
        if(!isValidBST(root->left) || root->val <= prev) return false;
        prev = root->val;
        return isValidBST(root->right);
    }
};